<!DOCTYPE html>





<html class="theme-next gemini" lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="generator" content="Hexo 3.9.0">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="32x32" href="/images/CNY32x32.png?v=7.3.0">
  <link rel="icon" type="image/png" sizes="16x16" href="/images/CNY16x16.png?v=7.3.0">
  <link rel="mask-icon" href="/images/logo.svg?v=7.3.0" color="#222">

<link rel="stylesheet" href="/css/main.css?v=7.3.0">


<link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css?v=4.7.0">


<script id="hexo-configurations">
  var NexT = window.NexT || {};
  var CONFIG = {
    root: '/',
    scheme: 'Gemini',
    version: '7.3.0',
    exturl: false,
    sidebar: {"position":"left","display":"post","offset":12,"onmobile":false},
    back2top: {"enable":true,"sidebar":false,"scrollpercent":true},
    save_scroll: false,
    copycode: {"enable":true,"show_result":true,"style":null},
    fancybox: false,
    mediumzoom: false,
    lazyload: false,
    pangu: false,
    algolia: {
      appID: '',
      apiKey: '',
      indexName: '',
      hits: {"per_page":10},
      labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
    },
    localsearch: {"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},
    path: 'search.xml',
    motion: {"enable":false,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
    translation: {
      copy_button: '复制',
      copy_success: '复制成功',
      copy_failure: '复制失败'
    }
  };
</script>

  <meta name="description" content="前言本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。远程仓库地址：https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph图的存储结构实现图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表">
<meta name="keywords" content="数据结构">
<meta property="og:type" content="article">
<meta property="og:title" content="基于Python的图算法实现">
<meta property="og:url" content="localhost:4000/2019/08/25/基于Python的图算法实现/index.html">
<meta property="og:site_name" content="钟浩伟的个人博客">
<meta property="og:description" content="前言本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。远程仓库地址：https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph图的存储结构实现图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表">
<meta property="og:locale" content="zh-CN">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190829183358.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190830224239.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831002634.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831190937.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831193520.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831193520.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831205632.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831210501.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831212236.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/1567257835949.png!blog">
<meta property="og:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831212504.png!blog">
<meta property="og:updated_time" content="2019-09-10T06:50:31.490Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="基于Python的图算法实现">
<meta name="twitter:description" content="前言本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。远程仓库地址：https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph图的存储结构实现图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表">
<meta name="twitter:image" content="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog">
  <link rel="canonical" href="localhost:4000/2019/08/25/基于Python的图算法实现/">


<script id="page-configurations">
  // https://hexo.io/docs/variables.html
  CONFIG.page = {
    sidebar: "",
    isHome: false,
    isPost: true,
    isPage: false,
    isArchive: false
  };
</script>

  <title>基于Python的图算法实现 | 钟浩伟的个人博客</title>
  








  <noscript>
  <style>
  .use-motion .motion-element,
  .use-motion .brand,
  .use-motion .menu-item,
  .sidebar-inner,
  .use-motion .post-block,
  .use-motion .pagination,
  .use-motion .comments,
  .use-motion .post-header,
  .use-motion .post-body,
  .use-motion .collection-title { opacity: initial; }

  .use-motion .logo,
  .use-motion .site-title,
  .use-motion .site-subtitle {
    opacity: initial;
    top: initial;
  }

  .use-motion .logo-line-before i { left: initial; }
  .use-motion .logo-line-after i { right: initial; }
  </style>
</noscript>

</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="zh-CN">

  <div class="container sidebar-position-left">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-brand-wrapper">
  <div class="site-meta">

    <div class="custom-logo-site-title">
      <a href="/" class="brand" rel="start">
        <span class="logo-line-before"><i></i></span>
        <span class="site-title">钟浩伟的个人博客</span>
        <span class="logo-line-after"><i></i></span>
      </a>
    </div>
        <p class="site-subtitle">欢迎光临</p>
      
  </div>

  <div class="site-nav-toggle">
    <button aria-label="切换导航栏">
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
      <span class="btn-bar"></span>
    </button>
  </div>
</div>


<nav class="site-nav">
  
  <ul id="menu" class="menu">
      
      
      
        
        <li class="menu-item menu-item-home">
      
    

    <a href="/" rel="section"><i class="menu-item-icon fa fa-fw fa-home"></i> <br>首页</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-tags">
      
    

    <a href="/tags/" rel="section"><i class="menu-item-icon fa fa-fw fa-tags"></i> <br>标签</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-categories">
      
    

    <a href="/categories/" rel="section"><i class="menu-item-icon fa fa-fw fa-th"></i> <br>分类</a>

  </li>
      
      
      
        
        <li class="menu-item menu-item-archives">
      
    

    <a href="/archives/" rel="section"><i class="menu-item-icon fa fa-fw fa-archive"></i> <br>归档</a>

  </li>
      <li class="menu-item menu-item-search">
        <a href="javascript:;" class="popup-trigger">
        
          <i class="menu-item-icon fa fa-search fa-fw"></i> <br>搜索</a>
      </li>
    
  </ul>

</nav>
  <div class="site-search">
    
  <div class="popup search-popup">
  <div class="search-header">
    <span class="search-icon">
      <i class="fa fa-search"></i>
    </span>
    <div class="search-input-wrapper">
      <input autocomplete="off" autocorrect="off" autocapitalize="none"
             placeholder="搜索..." spellcheck="false"
             type="text" id="search-input">
    </div>
    <span class="popup-btn-close">
      <i class="fa fa-times-circle"></i>
    </span>
  </div>
  <div id="search-result"></div>
</div>


  </div>
</div>
    </header>

    


    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
            

          <div id="content" class="content page-post-detail">
            

  <div id="posts" class="posts-expand">
    

  <article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
  
  
  
  <div class="post-block">
    <link itemprop="mainEntityOfPage" href="localhost:4000/2019/08/25/基于Python的图算法实现/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="name" content="钟浩伟">
      <meta itemprop="description" content="">
      <meta itemprop="image" content="/images/profile.jpg">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="钟浩伟的个人博客">
    </span>
      <header class="post-header">

        
          <h1 class="post-title" itemprop="name headline">基于Python的图算法实现

            
          </h1>
        

        <div class="post-meta">
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-calendar-o"></i>
              </span>
              <span class="post-meta-item-text">发表于</span>

              
                
              

              <time title="创建时间：2019-08-25 21:20:06" itemprop="dateCreated datePublished" datetime="2019-08-25T21:20:06+08:00">2019-08-25</time>
            </span>
          
            <span class="post-meta-item">
              <span class="post-meta-item-icon">
                <i class="fa fa-folder-o"></i>
              </span>
              <span class="post-meta-item-text">分类于</span>
              
                <span itemprop="about" itemscope itemtype="http://schema.org/Thing"><a href="/categories/计算机理论/" itemprop="url" rel="index"><span itemprop="name">计算机理论</span></a></span>

                
                
              
            </span>
          

          

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody">

      
        <h1 id="前言"><a href="#前言" class="headerlink" title="前言"></a>前言</h1><p>本来是想用C语言好好写的，可是指针和结构体太烦人了，弄得我头凉。因此决定用python实现一下图的一些算法。</p><p>远程仓库地址：</p><p><a href="https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph" target="_blank" rel="noopener">https://github.com/XiaoZhong233/DataStructure_Python/tree/master/graph</a></p><h1 id="图的存储结构实现"><a href="#图的存储结构实现" class="headerlink" title="图的存储结构实现"></a>图的存储结构实现</h1><p>图的实现有邻接矩阵，邻接表，十字链表等。我后面的算法主要用邻接表</p><a id="more"></a>



<p>建议直接看</p>
<p>[邻接表实现2，基于字典实现](# 邻接表实现2 (基于字典实现，好用))</p>
<p>首先定义了一个异常类：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GraphError</span><span class="params">(Exception)</span>:</span></span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure>

<h2 id="邻接矩阵实现（不重要也不好用）"><a href="#邻接矩阵实现（不重要也不好用）" class="headerlink" title="邻接矩阵实现（不重要也不好用）"></a>邻接矩阵实现（不重要也不好用）</h2><p>基于邻接矩阵定义了一个实现图的类，其中矩阵元素可以是1或者其他权值，表示有边，或者用一个特殊值表示“无关联”。构造参数的<code>unconn</code>就是表示无关联的值，默认为0。</p>
<p>图的构造函数的主要参数是<code>mat</code>,表示初始的邻接矩阵。要求是一个二维数组，且为方阵。代码如下</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># unconn 无关联参数</span></span><br><span class="line"><span class="comment"># 邻接矩阵实现</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Graph</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self, mat, unconn=<span class="number">0</span>)</span>:</span></span><br><span class="line">        vnum = len(mat)</span><br><span class="line">        <span class="comment"># 检查是否为方阵</span></span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> mat:</span><br><span class="line">            <span class="keyword">if</span> len(x) != vnum:</span><br><span class="line">                <span class="keyword">raise</span> ValueError(<span class="string">"参数错误：不为方阵"</span>)</span><br><span class="line">        <span class="comment"># 拷贝数据</span></span><br><span class="line">        self._mat = [mat[i][:] <span class="keyword">for</span> i <span class="keyword">in</span> range(vnum)]</span><br><span class="line">        self._unconn = unconn</span><br><span class="line">        self._vnum = vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 返回顶点数目</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">vertex_num</span><span class="params">(self)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> self._vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 检查该顶点是否合法，也就是下标是否找得到</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_invalid</span><span class="params">(self, v)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> v &lt; <span class="number">0</span> <span class="keyword">or</span> v &gt;= self._vnum</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 加入新的顶点</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_vertex</span><span class="params">(self)</span>:</span></span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">"邻接矩阵不支持加入顶点"</span>)</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 加入新的边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_edge</span><span class="params">(self, vi, vj, val=<span class="number">1</span>)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi) <span class="keyword">or</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line">        self._mat[vi][vj] = val</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某条边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_edge</span><span class="params">(self, vi, vj)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi) <span class="keyword">or</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line">        <span class="keyword">return</span> self._mat[vi][vj]</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某个顶点的出边</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">out_edges</span><span class="params">(self, vi)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vi):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line">        <span class="keyword">return</span> self.out_edge(self._mat[vi], self._unconn)</span><br><span class="line">	</span><br><span class="line">	<span class="comment"># 获得某个顶点的出边</span></span><br><span class="line"><span class="meta">    @staticmethod</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_out_edges</span><span class="params">(row, unconn)</span>:</span></span><br><span class="line">        edges = []</span><br><span class="line">        <span class="keyword">for</span> i <span class="keyword">in</span> range(len(row)):</span><br><span class="line">            <span class="keyword">if</span> row[i] != unconn:</span><br><span class="line">                edges.append((i, row[i]))</span><br><span class="line">        <span class="keyword">return</span> edges</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__str__</span><span class="params">(self)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> <span class="string">"[\n"</span> + <span class="string">",\n"</span>.join(map(str, self._mat)) + <span class="string">"\n]"</span> \</span><br><span class="line">               + <span class="string">"\nUnconnected: "</span> + str(self._unconn)</span><br></pre></td></tr></table></figure>

<p>这个简单的邻接矩阵实现的图类并未支持增加顶点，因为邻接矩阵增加顶点要增加多一行一列，挺麻烦的，就不想写了。</p>
<h2 id="邻接表实现1（基于邻接矩阵，不好用）"><a href="#邻接表实现1（基于邻接矩阵，不好用）" class="headerlink" title="邻接表实现1（基于邻接矩阵，不好用）"></a>邻接表实现1（基于邻接矩阵，不好用）</h2><p>邻接矩阵的缺点是占用空间很多，如果是稀疏图就很难受了，可能会有很大的空间损失，因此常用邻接表实现图的存储。在上面邻接矩阵的实现下，可考虑一种“压缩后”的邻接表实现。</p>
<figure class="highlight ruby"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 邻接表实现（压缩邻接矩阵形式）</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GraphAL</span>(<span class="title">Graph</span>):</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(<span class="keyword">self</span>, mat=[], unconn=<span class="number">0</span>)</span></span><span class="symbol">:</span></span><br><span class="line">        vnum = len(mat)</span><br><span class="line">        <span class="keyword">for</span> x <span class="keyword">in</span> <span class="symbol">mat:</span></span><br><span class="line">            <span class="keyword">if</span> len(x) != <span class="symbol">vnum:</span></span><br><span class="line">                raise ValueError(<span class="string">"参数错误：不为方阵"</span>)</span><br><span class="line">        <span class="keyword">self</span>._mat = [Graph._out_edges(mat[i], unconn) <span class="keyword">for</span> i <span class="keyword">in</span> range(vnum)]</span><br><span class="line">        <span class="keyword">self</span>._vnum = vnum</span><br><span class="line">        <span class="keyword">self</span>._unconn = unconn</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_vertex</span><span class="params">(<span class="keyword">self</span>)</span></span><span class="symbol">:</span></span><br><span class="line">        <span class="keyword">self</span>._mat.append([])</span><br><span class="line">        <span class="keyword">self</span>._vnum += <span class="number">1</span></span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">self</span>._vnum - <span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_edge</span><span class="params">(<span class="keyword">self</span>, vi, vj, val=<span class="number">1</span>)</span></span><span class="symbol">:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">self</span>._vnum == <span class="number">0</span><span class="symbol">:</span></span><br><span class="line">            raise GraphError(<span class="string">"无法为空图增加边"</span>)</span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">self</span>._invalid(vi) <span class="keyword">or</span> <span class="keyword">self</span>._invalid(vj)<span class="symbol">:</span></span><br><span class="line">            raise GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line"></span><br><span class="line">        row = <span class="keyword">self</span>._mat[vi]</span><br><span class="line">        i = <span class="number">0</span></span><br><span class="line">        <span class="keyword">while</span> i &lt; len(row)<span class="symbol">:</span></span><br><span class="line">            <span class="keyword">if</span> row[i][<span class="number">0</span>] == <span class="symbol">vj:</span></span><br><span class="line">                <span class="keyword">self</span>._mat[vi][i] = (vj, val)</span><br><span class="line">                <span class="keyword">return</span></span><br><span class="line">            <span class="keyword">if</span> row[i][<span class="number">0</span>] &gt; <span class="symbol">vj:</span>  <span class="comment"># 没有到与vj的边，退出循环加入边</span></span><br><span class="line">                <span class="keyword">break</span></span><br><span class="line">            i += <span class="number">1</span></span><br><span class="line">        <span class="keyword">self</span>._mat[vi].insert(i, (vj, val))</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_edge</span><span class="params">(<span class="keyword">self</span>, vi, vj)</span></span><span class="symbol">:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">self</span>._invalid(vi) <span class="keyword">or</span> <span class="keyword">self</span>._invalid(vj)<span class="symbol">:</span></span><br><span class="line">            raise GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line">        <span class="keyword">for</span> i, val <span class="keyword">in</span> <span class="keyword">self</span>._mat[vi]<span class="symbol">:</span></span><br><span class="line">            <span class="keyword">if</span> i == <span class="symbol">vj:</span></span><br><span class="line">                <span class="keyword">return</span> val</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">self</span>._unconn</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">out_edges</span><span class="params">(<span class="keyword">self</span>, vi)</span></span><span class="symbol">:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">self</span>._invalid(vi)<span class="symbol">:</span></span><br><span class="line">            raise GraphError(<span class="string">"顶点不合法"</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="keyword">self</span>._mat[vi]</span><br></pre></td></tr></table></figure>

<h2 id="邻接表实现2-基于字典实现，好用"><a href="#邻接表实现2-基于字典实现，好用" class="headerlink" title="邻接表实现2 (基于字典实现，好用)"></a>邻接表实现2 (基于字典实现，好用)</h2><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog" alt="20190825160305"></p>
<p>数据格式如图所示：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">graph = &#123;</span><br><span class="line">    <span class="string">"A"</span>: &#123;<span class="string">"B"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"B"</span>: &#123;<span class="string">"A"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"C"</span>: &#123;<span class="string">"A"</span>: <span class="number">1</span>, <span class="string">"B"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">"D"</span>: &#123;<span class="string">"B"</span>: <span class="number">1</span>, <span class="string">"C"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">3</span>, <span class="string">"F"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">"E"</span>: &#123;<span class="string">"C"</span>: <span class="number">8</span>, <span class="string">"D"</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">"F"</span>: &#123;<span class="string">"D"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>如上图所示，该类是一个无向网，如果需要改成有向网，只需要更改<code>add_edge</code>这个方法</p>
<p>新建一个<code>GraphAL.py</code>文件，在文件中添加：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 邻接表实现无向网（图）（字典形式）</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">GraphAL</span>:</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">__init__</span><span class="params">(self, graph=&#123;&#125;)</span>:</span></span><br><span class="line">        self._graph = graph</span><br><span class="line">        self._vnum = len(graph)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">_invalid</span><span class="params">(self, vertex)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> self._graph.__contains__(vertex)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_vertex</span><span class="params">(self, vertex)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> self._invalid(vertex):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"添加顶点失败，已经有该顶点"</span>)</span><br><span class="line">        self._graph[vertex] = &#123;&#125;</span><br><span class="line">        self._vnum += <span class="number">1</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">add_edge</span><span class="params">(self, vi, vj, val)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vi) <span class="keyword">or</span> <span class="keyword">not</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + vi + <span class="string">"或者"</span> + vj + <span class="string">"这样的顶点"</span>)</span><br><span class="line">        self._graph[vi].update(&#123;vj: val&#125;)</span><br><span class="line">        self._graph[vj].update(&#123;vi: val&#125;)</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_edge</span><span class="params">(self, vi, vj)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vi) <span class="keyword">or</span> <span class="keyword">not</span> self._invalid(vj):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + vi + <span class="string">"或者"</span> + vj + <span class="string">"这样的顶点"</span>)</span><br><span class="line">        <span class="keyword">return</span> self._graph[vi][vj]</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">get_vertexNum</span><span class="params">(self)</span>:</span></span><br><span class="line">        <span class="keyword">return</span> self._graph.__len__()</span><br><span class="line"></span><br><span class="line">    <span class="comment"># 在无向网（图）中是边，有向网（图）是出边，取决于数据</span></span><br><span class="line">    <span class="function"><span class="keyword">def</span> <span class="title">out_edge</span><span class="params">(self, vertex)</span>:</span></span><br><span class="line">        <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(vertex):</span><br><span class="line">            <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + vertex + <span class="string">"这样的顶点"</span>)</span><br><span class="line">        <span class="keyword">return</span> self._graph[vertex]</span><br></pre></td></tr></table></figure>

<p>你也可以不传入图的参数，会默认创建一个新图。通过<code>add_vertex</code>和<code>add_edge</code>即可完成图的构建。</p>
<h1 id="图的一些算法实现"><a href="#图的一些算法实现" class="headerlink" title="图的一些算法实现"></a>图的一些算法实现</h1><h2 id="图的遍历"><a href="#图的遍历" class="headerlink" title="图的遍历"></a>图的遍历</h2><h3 id="BFS（广度优先搜索）"><a href="#BFS（广度优先搜索）" class="headerlink" title="BFS（广度优先搜索）"></a>BFS（广度优先搜索）</h3><h4 id="算法原理及步骤"><a href="#算法原理及步骤" class="headerlink" title="算法原理及步骤"></a>算法原理及步骤</h4><p>按照广度优先原则遍历图，利用了队列，有点像树的层次遍历。广度优先遍历的结果不唯一。整个遍历过程大概是这样的：给定一个起始顶点，将该起始顶点入队</p>
<ol>
<li>顶点出队，如果当前顶点未被标记访问，则访问该顶点，然后标记为已访问，如果当前顶点已访问则直接丢弃该顶点</li>
<li>当前访问顶点的邻接顶点入队</li>
<li>当队列不为空的时候，循环1,2步</li>
</ol>
<h4 id="算法流程"><a href="#算法流程" class="headerlink" title="算法流程"></a>算法流程</h4><pre class="mermaid">graph LR
    start(起始点入队)
    deque[出队]
    isVisit{未被访问?}
    visit(访问该结点并输出)
    isnull[检查队空]
    end1((结束))

start-->deque
deque-->isVisit
isVisit--未被访问-->visit
isVisit--已经被访问-->deque
isnull-->end1
visit-->isnull
isnull--不为空-->deque</pre>



<div id="flowchart-0" class="flow-chart"></div>






<h4 id="算法实现"><a href="#算法实现" class="headerlink" title="算法实现"></a>算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 广度优先遍历</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">bfs</span><span class="params">(self, start)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + start + <span class="string">"这样的顶点"</span>)</span><br><span class="line">    queue = [start]  <span class="comment"># 队列实现BFS</span></span><br><span class="line">    seen = set(start)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># Node代表根节点，数组形式保存树</span></span><br><span class="line">    result = []</span><br><span class="line">    <span class="keyword">while</span> queue.__len__() &gt; <span class="number">0</span>:  <span class="comment"># 队非空时</span></span><br><span class="line">        vertex = queue.pop(<span class="number">0</span>)  <span class="comment"># 队首顶点出队</span></span><br><span class="line">        nodes = self._graph[vertex]  <span class="comment"># 获得其邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                queue.append(node)  <span class="comment"># 其邻接顶点如果没有被访问，则入队，并且保留父顶点</span></span><br><span class="line">                seen.add(node)</span><br><span class="line">                parent[node] = vertex</span><br><span class="line">        result.append(vertex)</span><br><span class="line">    <span class="keyword">return</span> result, parent</span><br></pre></td></tr></table></figure>

<h4 id="测试"><a href="#测试" class="headerlink" title="测试"></a>测试</h4><p>例如遍历下图</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog" alt="20190825160305"></p>
<p>具体的存储结构为：</p>
<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">data = &#123;</span><br><span class="line">    <span class="string">"A"</span>: &#123;<span class="string">"B"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"B"</span>: &#123;<span class="string">"A"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"C"</span>: &#123;<span class="string">"A"</span>: <span class="number">1</span>, <span class="string">"B"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">"D"</span>: &#123;<span class="string">"B"</span>: <span class="number">1</span>, <span class="string">"C"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">3</span>, <span class="string">"F"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">"E"</span>: &#123;<span class="string">"C"</span>: <span class="number">8</span>, <span class="string">"D"</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">"F"</span>: &#123;<span class="string">"D"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">test_bfs</span><span class="params">(self)</span>:</span></span><br><span class="line">    print(<span class="string">"bfs测试："</span>)</span><br><span class="line">    bfs, bfsparent = TestGraph.g.bfs(<span class="string">"A"</span>)</span><br><span class="line">    print(<span class="string">"BFS:"</span> + graph.GraphAL.printPath(bfs))</span><br><span class="line">    print(<span class="string">"BFS生成路径:"</span> + bfsparent.__str__())</span><br><span class="line">    print(<span class="string">"BFS生成路径打印："</span> + graph.GraphAL.printTreePath(bfsparent).__str__())</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure>

<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190829183358.png!blog" alt="20190829183358"></p>
<h3 id="DFS（深度优先搜索）"><a href="#DFS（深度优先搜索）" class="headerlink" title="DFS（深度优先搜索）"></a>DFS（深度优先搜索）</h3><h4 id="算法原理及步骤-1"><a href="#算法原理及步骤-1" class="headerlink" title="算法原理及步骤"></a>算法原理及步骤</h4><p>DFS和BFS很像，不过DFS是深度优先的原则，具体实现是栈。</p>
<p>DFS遍历的结果不唯一。整个遍历过程大概是这样的：给定一个起始顶点，将该起始顶点入栈</p>
<ol>
<li>顶点出栈，如果当前顶点未被标记访问，则访问该顶点，然后标记为已访问，如果当前顶点已访问则直接丢弃该顶点</li>
<li>当前访问顶点的邻接顶点入栈</li>
<li>当栈不为空的时候，循环1,2步</li>
</ol>
<h4 id="算法流程-1"><a href="#算法流程-1" class="headerlink" title="算法流程"></a>算法流程</h4><pre class="mermaid">graph LR
    start(起始点入栈)
    deque[出栈]
    isVisit{未被访问?}
    visit(访问该结点并输出)
    isnull[检查栈空]
    end1((结束))

start-->deque
deque-->isVisit
isVisit--未被访问-->visit
isVisit--已经被访问-->deque
isnull-->end1
visit-->isnull
isnull--不为空-->deque</pre>



<div id="flowchart-1" class="flow-chart"></div>



<h4 id="算法实现-1"><a href="#算法实现-1" class="headerlink" title="算法实现"></a>算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 深度优先遍历</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dfs</span><span class="params">(self, start)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + start + <span class="string">"这样的顶点"</span>)</span><br><span class="line">    stack = [start]  <span class="comment"># 栈实现DFS</span></span><br><span class="line">    seen = set(start)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># Node代表根节点，数组形式保存树</span></span><br><span class="line">    result = []</span><br><span class="line">    <span class="keyword">while</span> stack.__len__() &gt; <span class="number">0</span>:  <span class="comment"># 栈非空时</span></span><br><span class="line">        vertex = stack.pop()  <span class="comment"># 顶点出栈</span></span><br><span class="line">        nodes = self._graph[vertex]  <span class="comment"># 获取出栈顶点的邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                stack.append(node)</span><br><span class="line">                seen.add(node)</span><br><span class="line">                parent[node] = vertex</span><br><span class="line">        result.append(vertex)</span><br><span class="line">    <span class="keyword">return</span> result, parent</span><br></pre></td></tr></table></figure>

<h4 id="测试-1"><a href="#测试-1" class="headerlink" title="测试"></a>测试</h4><p>例如遍历下图</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog" alt="20190825160305"></p>
<h5 id="存储结构"><a href="#存储结构" class="headerlink" title="存储结构"></a>存储结构</h5><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">data = &#123;</span><br><span class="line">    <span class="string">"A"</span>: &#123;<span class="string">"B"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"B"</span>: &#123;<span class="string">"A"</span>: <span class="number">5</span>, <span class="string">"C"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">1</span>&#125;,</span><br><span class="line">    <span class="string">"C"</span>: &#123;<span class="string">"A"</span>: <span class="number">1</span>, <span class="string">"B"</span>: <span class="number">2</span>, <span class="string">"D"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">8</span>&#125;,</span><br><span class="line">    <span class="string">"D"</span>: &#123;<span class="string">"B"</span>: <span class="number">1</span>, <span class="string">"C"</span>: <span class="number">4</span>, <span class="string">"E"</span>: <span class="number">3</span>, <span class="string">"F"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">    <span class="string">"E"</span>: &#123;<span class="string">"C"</span>: <span class="number">8</span>, <span class="string">"D"</span>: <span class="number">3</span>&#125;,</span><br><span class="line">    <span class="string">"F"</span>: &#123;<span class="string">"D"</span>: <span class="number">6</span>&#125;,</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h5 id="测试结果"><a href="#测试结果" class="headerlink" title="测试结果"></a>测试结果</h5><figure class="highlight"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line">图的结构为：</span><br><span class="line">(<span class="string">'A'</span>, &#123;<span class="string">'B'</span>: <span class="number">5</span>, <span class="string">'C'</span>: <span class="number">1</span>&#125;)</span><br><span class="line">(<span class="string">'B'</span>, &#123;<span class="string">'A'</span>: <span class="number">5</span>, <span class="string">'C'</span>: <span class="number">2</span>, <span class="string">'D'</span>: <span class="number">1</span>&#125;)</span><br><span class="line">(<span class="string">'C'</span>, &#123;<span class="string">'A'</span>: <span class="number">1</span>, <span class="string">'B'</span>: <span class="number">2</span>, <span class="string">'D'</span>: <span class="number">4</span>, <span class="string">'E'</span>: <span class="number">8</span>&#125;)</span><br><span class="line">(<span class="string">'D'</span>, &#123;<span class="string">'B'</span>: <span class="number">1</span>, <span class="string">'C'</span>: <span class="number">4</span>, <span class="string">'E'</span>: <span class="number">3</span>, <span class="string">'F'</span>: <span class="number">6</span>&#125;)</span><br><span class="line">(<span class="string">'E'</span>, &#123;<span class="string">'C'</span>: <span class="number">8</span>, <span class="string">'D'</span>: <span class="number">3</span>&#125;)</span><br><span class="line">(<span class="string">'F'</span>, &#123;<span class="string">'D'</span>: <span class="number">6</span>&#125;)</span><br><span class="line"></span><br><span class="line">dfs测试：</span><br><span class="line">DFS:A-&gt;C-&gt;E-&gt;D-&gt;F-&gt;B</span><br><span class="line">DFS生成路径:&#123;<span class="string">'A'</span>: <span class="literal">None</span>, <span class="string">'B'</span>: <span class="string">'A'</span>, <span class="string">'C'</span>: <span class="string">'A'</span>, <span class="string">'D'</span>: <span class="string">'C'</span>, <span class="string">'E'</span>: <span class="string">'C'</span>, <span class="string">'F'</span>: <span class="string">'D'</span>&#125;</span><br><span class="line">DFS生成路径打印：</span><br><span class="line">A-&gt;B</span><br><span class="line">A-&gt;C</span><br><span class="line">A-&gt;C-&gt;D</span><br><span class="line">A-&gt;C-&gt;E</span><br><span class="line">A-&gt;C-&gt;D-&gt;F</span><br></pre></td></tr></table></figure>

<h2 id="最小生成树"><a href="#最小生成树" class="headerlink" title="最小生成树"></a>最小生成树</h2><p>最小生成树针对的是连通网而言的。假定一个网络G，他的边带有权值，自然可以通过BFS,DFS获得他的生成树，权值最小的那棵树，就称最小生成树</p>
<p>最小生成树有许多实际的应用，例如通信网，输电网及各种网的规划。</p>
<h3 id="Prim算法"><a href="#Prim算法" class="headerlink" title="Prim算法"></a>Prim算法</h3><h4 id="算法原理及算法流程"><a href="#算法原理及算法流程" class="headerlink" title="算法原理及算法流程"></a>算法原理及算法流程</h4><h5 id="原理："><a href="#原理：" class="headerlink" title="原理："></a>原理：</h5><p>根据（MST性质：网络G必有一颗最小生成树），具体证明不再赘述，大概思想就是假设你现有一个图的集合G，从G中的一个顶点出发，不断的选择最短的一条连接边，扩充到已选边集N中，直至N包含了图G中的所有顶点。</p>
<h5 id="构造过程举例"><a href="#构造过程举例" class="headerlink" title="构造过程举例"></a>构造过程举例</h5><p>假设现在有这样一颗图</p>
<pre class="mermaid">graph RL
    V1((V1))
    V2((V2))
    V3((V3))
    V4((V4))
    V5((V5))
    V6((V6))
V1--6---V2
V1--1---V3
V1--5---V4
V2--5---V3
V3--5---V4
V3--6---V5
V3--4---V6</pre>

<p>要对该图进行prim算法进行最小生成树。首先找一个开始顶点，假设从<code>V1</code>开始</p>
<h6 id="第一次构造"><a href="#第一次构造" class="headerlink" title="第一次构造"></a>第一次构造</h6><p>V1的邻接节点全部入队。并且由于该队列是优先级队列，会按照权重排序</p>
<pre class="mermaid">graph LR
    V13((v1,v3,1))
    V14((v1,v4,5))
    V12((v1,v2,6))

V13-->V14
V14-->V12</pre>

<p>队首出队，构造边，将该边加入到N集</p>
<p>此时N集中就有了一条边了</p>
<pre class="mermaid">graph TB
    V1((v1))
    V3((V3))
V1--1---V3</pre>



<p><code>V3</code>除了N集中的结点的邻接节点入队，优先队列会按照权重进行排序</p>
<pre class="mermaid">graph LR
    V32((v3,v2,5))
    V34((v3,v4,5))
    V35((v3,v5,6))
    V36((v3,v6,4))
    V14((v1,v4,5))
    V12((v1,v2,6))
V36-->V14
V14-->V32
V32-->V34
V34-->V12
V12-->V35</pre>



<h6 id="第二次构造"><a href="#第二次构造" class="headerlink" title="第二次构造"></a>第二次构造</h6><p>队首出队，构造边，将该边加入到N集</p>
<p>此时N集有两条边了</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
V1--1---V3
V3--4---V6</pre>



<p>将<code>V6</code>的除N集中已有的邻接节点入队，</p>
<pre class="mermaid">graph LR
    V64((v6,v4,2))
    V65((V6,V5,6))
    V32((v3,v2,5))
    V34((v3,v4,5))
    V35((v3,v5,6))
    V14((v1,v4,5))
    V12((v1,v2,6))
V64-->V14
V14-->V32
V32-->V34
V34-->V12
V12-->V35
V35-->V65</pre>



<h6 id="第三次构造"><a href="#第三次构造" class="headerlink" title="第三次构造"></a>第三次构造</h6><p>队首出队，构造边，将该边&lt;6,4&gt;加入到N集</p>
<p>此时的N集就有三条边了</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
V1--1---V3
V3--4---V6
V6--2---V4</pre>



<p>将<code>V4</code>的除N集中已有的邻接节点入队,发现v4的邻接顶点都在N集中了，所以没有顶点入队</p>
<pre class="mermaid">graph LR
    V65((V6,V5,6))
    V32((v3,v2,5))
    V34((v3,v4,5))
    V35((v3,v5,6))
    V14((v1,v4,5))
    V12((v1,v2,6))
V14-->V32
V32-->V34
V34-->V12
V12-->V35
V35-->V65</pre>



<h6 id="第四次构造"><a href="#第四次构造" class="headerlink" title="第四次构造"></a>第四次构造</h6><p>队首<code>&lt;v1,v4&gt;</code>出队，构造边，将该边<code>&lt;v1,v4&gt;</code>加入到N集，注意此时由于<code>&lt;v1,v4&gt;</code>加入N集中会构成连通，<strong>所以跳过本次构造边</strong>。</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
V1--1---V3
V3--4---V6
V6--2---V4
V1--5---V4</pre>

<p>所以，当前N集中的边还是和原来一样，如下图：</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
V1--1---V3
V3--4---V6
V6--2---V4</pre>



<p>将<code>V4</code>的除N集中已有的邻接节点入队,发现v4的邻接顶点都在N集中了，所以没有顶点入队</p>
<pre class="mermaid">graph LR
    V65((V6,V5,6))
    V32((v3,v2,5))
    V34((v3,v4,5))
    V35((v3,v5,6))
    V12((v1,v2,6))
V32-->V34
V34-->V12
V12-->V35
V35-->V65</pre>



<h6 id="第五次构造"><a href="#第五次构造" class="headerlink" title="第五次构造"></a>第五次构造</h6><p>队首<code>&lt;v3,v2&gt;</code>出队，构造边，将该边加入到N集中。</p>
<p>此时N集就有五条边了</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
V1--1---V3
V3--4---V6
V6--2---V4
V3--5---V2</pre>

<p>将<code>V2</code>的除N集中已有的邻接节点入队</p>
<pre class="mermaid">graph LR
    V65((V6,V5,6))
    V32((v3,v2,5))
    V34((v3,v4,5))
    V35((v3,v5,6))
    V12((v1,v2,6))
    V25((V2,V5,3))
V32-->V34
V34-->V12
V12-->V35
V35-->V65
V25-->V32</pre>



<h6 id="第六次构造"><a href="#第六次构造" class="headerlink" title="第六次构造"></a>第六次构造</h6><p>队首<code>&lt;v2,v5&gt;</code>出队，构造边，加入边到N集中。此时N集中有5条边。由于总共就6个顶点，当构成最小生成树的时候边只能是5条，你如果在加一条边就连通了，所以prim构造生成树结束</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V3--4---V6
V6--2---V4
V3--5---V2
V2--3---V5</pre>



<h6 id="最终结果"><a href="#最终结果" class="headerlink" title="最终结果"></a>最终结果</h6><pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V3--4---V6
V6--2---V4
V3--5---V2
V2--3---V5</pre>







<h4 id="算法实现-2"><a href="#算法实现-2" class="headerlink" title="算法实现"></a>算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># prim算法，最小生成树，前提该图必须是连通网</span></span><br><span class="line"> <span class="function"><span class="keyword">def</span> <span class="title">prim</span><span class="params">(self, start)</span>:</span></span><br><span class="line">     <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">         <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + start + <span class="string">"这样的顶点"</span>)</span><br><span class="line">     result = GraphAL(&#123;&#125;)</span><br><span class="line">     edgeCount = <span class="number">0</span></span><br><span class="line">     pqueue = []  <span class="comment"># 优先级队列,候选列表</span></span><br><span class="line">     <span class="comment"># 初始化优先级队列</span></span><br><span class="line">     <span class="keyword">for</span> node <span class="keyword">in</span> self._graph[start]:</span><br><span class="line">         heapq.heappush(pqueue, (self._graph[start][node], start, node))</span><br><span class="line">         <span class="keyword">pass</span></span><br><span class="line">     <span class="keyword">while</span> edgeCount &lt; self.get_vertexNum() - <span class="number">1</span> <span class="keyword">and</span> <span class="keyword">not</span> pqueue.__len__() == <span class="number">0</span>:</span><br><span class="line">         <span class="comment"># 出队</span></span><br><span class="line">         pair = heapq.heappop(pqueue)</span><br><span class="line">         distance = pair[<span class="number">0</span>]</span><br><span class="line">         start = pair[<span class="number">1</span>]</span><br><span class="line">         end = pair[<span class="number">2</span>]</span><br><span class="line">         <span class="comment"># 判断是否有该顶点,如果没有就要加入</span></span><br><span class="line">         <span class="keyword">if</span> start <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">             result.add_vertex(start)</span><br><span class="line">         <span class="keyword">if</span> end <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">             result.add_vertex(end)</span><br><span class="line">         <span class="comment"># 如果当前点与下一节点未建立边，则尝试建立边</span></span><br><span class="line">         <span class="comment"># 方式是检查下一节点是否在result中，如果有则说明这个节点已经建立过边了，再建立边的话会可能会形成连通，因此直接舍弃该边的建立</span></span><br><span class="line">         <span class="keyword">if</span> end <span class="keyword">not</span> <span class="keyword">in</span> result._graph[start]:</span><br><span class="line">             <span class="comment"># 如果下一个节点如果未被其他节点连接则result._graph[end]返回false，开始构造边，</span></span><br><span class="line">             <span class="comment"># 如果下一个节点已经被连接了，则result._graph[end]返回true，舍弃该边的建立</span></span><br><span class="line">             <span class="keyword">if</span> <span class="keyword">not</span> result._graph[end]:</span><br><span class="line">                 result.add_edge(start, end, distance)</span><br><span class="line">                 edgeCount += <span class="number">1</span></span><br><span class="line">                 <span class="keyword">pass</span></span><br><span class="line">         start = end</span><br><span class="line">         <span class="comment"># 子节点入队</span></span><br><span class="line">         <span class="keyword">for</span> node <span class="keyword">in</span> self._graph[start]:</span><br><span class="line">             <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">                 heapq.heappush(pqueue, (self._graph[start][node], start, node))</span><br><span class="line">         <span class="keyword">pass</span></span><br><span class="line">     <span class="keyword">return</span> result</span><br></pre></td></tr></table></figure>

<h4 id="测试-2"><a href="#测试-2" class="headerlink" title="测试"></a>测试</h4><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190830224239.png!blog" alt="20190830224239"></p>
<p>与刚才流程构造的结果一致</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V3--4---V6
V6--2---V4
V3--5---V2
V2--3---V5</pre>





<h3 id="克鲁斯卡尔算法"><a href="#克鲁斯卡尔算法" class="headerlink" title="克鲁斯卡尔算法"></a>克鲁斯卡尔算法</h3><h4 id="算法原理及流程"><a href="#算法原理及流程" class="headerlink" title="算法原理及流程"></a>算法原理及流程</h4><h5 id="原理"><a href="#原理" class="headerlink" title="原理"></a>原理</h5><p>在一个连通图中不断选取权值最小的边，然后连起来，就是这样。</p>
<p>假设给定图G，结果图T</p>
<p>基本步骤如下：</p>
<ol>
<li>将G中的所有边按权值递增的顺序进行排序</li>
<li>选择权值最短的边且边的两端点属于不同连通分量（如果两端点属于同一个连通分量中，那么就说明该子图是连通图！所以不行），然后该边与T中已选择的边进行连接，每次边连接都会使得T的连通分量减1</li>
<li>当边数小于顶点数时，不断重复1,2</li>
</ol>
<p>如果当做完上面这些步骤后，得出的结果T中不能包含G中的所有顶点，则说明原图G是不连通的（也就是不是任意一个节点到另一个节点都走的通）</p>
<p>这里有两个难点：</p>
<ol>
<li><p>最短边的选取</p>
<p>思路①：采用优先队列，在python中可以通过优先级队列实现，其他语言像C++,Java中也有类似实现的数据结构。</p>
<p>思路②：不断的扫描候选边列表，然后进行排序。这种方法就比较麻烦了，写的代码比较多，不过也很灵活，具体排序方式你可以选择。</p>
</li>
<li><p>如何判断边的两个端点的连通分量</p>
<p>思路①：不断的检查两个端点之间是否有路径，有路径就说明在同一个子图中，连通分量相同。不过这样也太麻烦了点还浪费计算时间</p>
<p>思路②：前人提出的一种方法，为每个连通分量确定一个代表元，如果两个顶点的代表元相同，则表示他们连通成环。例如下图</p>
<pre class="mermaid">   graph TD
    V1((v1))
    V2((V2))
    V3((V3))
    V4((V4))</pre>

<p>当初始化的时候<code>v1,v2,v3,v4</code>的代表元就是他们的序号也就对应<code>0,1,2,3</code></p>
<p>当<code>v1</code>  <code>v2</code> 构成新边的时候，就要把<code>v2</code>的代表元改为<code>v1</code> 的代表元<code>0</code> 。</p>
<p>这时候<code>v1,v2,v3,v4</code>的代表元就更新为<code>0,0,2,3</code></p>
<pre class="mermaid">   graph TD
    V1((v1))
    V2((V2))
    V3((V3))
    V4((V4))
V1---V2</pre>

<p><code>v1</code> <code>v2</code>是的连通分量相同并且他们的代表元也是相同的。</p>
<p>类似，如果想要连接<code>v2</code> <code>v3</code>，此时<code>v2</code> <code>v3</code> 的代表元不同，因此连接了也不会构成环。 直接把<code>v3</code>的代表元修改为<code>v2</code>的代表元即可，即<code>0</code></p>
<pre class="mermaid">   graph LR
    V1((v1))
    V2((V2))
    V3((V3))
    V4((V4))
V1---V2
V2---V3</pre>

<p>此时<code>v1</code> <code>v2</code> <code>v3</code>是连通的，他们的代表元是<code>0,0,0</code></p>
<p>如果下一次操作中，想要把<code>v3</code> 连接到<code>v1</code> ，检查他们的代表元，都是<code>0</code>所以连接起来一定会构成环</p>
<pre class="mermaid">   graph LR
    V1((v1))
    V2((V2))
    V3((V3))
    V4((V4))
V1---V2
V2---V3
V3---V1</pre>

<p>因此，可以使用代表元判断欲加入的边是否会与已选择集合T中的边构成环路。</p>
</li>
</ol>
<h5 id="构成过程举例"><a href="#构成过程举例" class="headerlink" title="构成过程举例"></a>构成过程举例</h5><p>假设还是之前的这颗图G，其结果集T中目前还为空</p>
<pre class="mermaid">graph RL
    V1((V1))
    V2((V2))
    V3((V3))
    V4((V4))
    V5((V5))
    V6((V6))
V1--6---V2
V1--1---V3
V1--5---V4
V2--5---V3
V3--5---V4
V3--6---V5
V3--4---V6</pre>



<h6 id="初始化"><a href="#初始化" class="headerlink" title="初始化"></a>初始化</h6><p>全部边入队，自动在优先队列中根据权值排好序</p>
<pre class="mermaid">graph LR
    v46((v4,v6,2))
    v56((V5,V6,6))
    v32((v2,v3,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v36((v3,v6,4))
    v25((v2,v5,3))
    v14((v1,v4,5))
    v12((v1,v2,6))
    v13((v1,v3,1))
v13---v46
v46---v25
v25---v36
v36---v14
v14---v34
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<p>并且初始化代表元列表，初始值为他们的下标。</p>
<p>例如<code>v1</code>的代表元初始值为1，<code>v2</code>的代表元初始值为2….<code>vn</code>的代表元初始值为n</p>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,3]
    v4[v4,4]
    v5[v5,5]
    v6[v6,6]</pre>



<h6 id="第一次构造-1"><a href="#第一次构造-1" class="headerlink" title="第一次构造"></a>第一次构造</h6><ol>
<li>队首出队，所以<code>&lt;v1,v3&gt;</code>边出队</li>
</ol>
<pre class="mermaid">graph LR
    v64((v6,v4,2))
    v65((V6,V5,6))
    v32((v3,v2,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v36((v3,v6,4))
    v25((v2,v5,3))
    v14((v1,v4,5))
    v12((v1,v2,6))
    v13((v1,v3,1))
v13---v64
v64---v25
v25---v36
v36---v14
v14---v34
v34---v32
v32---v12
v12---v35
v35---v65</pre>



<ol>
<li>检查<code>v1</code>  <code>v3</code>的代表元，很明显不同,所以将<code>&lt;v1,v3&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
V1--1---V3</pre>

<ol start="3">
<li>合并代表元,修改等于代表元值为3的代表元的值，改为<code>v1</code>的代表元即1</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,4]
    v5[v5,5]
    v6[v6,6]</pre>



<h6 id="第二次构造-1"><a href="#第二次构造-1" class="headerlink" title="第二次构造"></a>第二次构造</h6><ol>
<li>队首出队，所以<code>&lt;v4,v6&gt;</code>边出队</li>
</ol>
<pre class="mermaid">graph LR
    v46((v4,v6,2))
    v56((V5,V6,6))
    v32((v2,v3,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v36((v3,v6,4))
    v25((v2,v5,3))
    v14((v1,v4,5))
    v12((v1,v2,6))


v46---v25
v25---v36
v36---v14
v14---v34
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v4</code>  <code>v6</code>的代表元，很明显不同,所以将<code>&lt;v4,v6&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
V1--1---V3
V6--2---V4</pre>

<ol start="3">
<li>合并代表元,修改等于代表元值为6的代表元的值，改为<code>v4</code>的代表元的值即4</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,4]
    v5[v5,5]
    v6[v6,4]</pre>



<h6 id="第三次构造-1"><a href="#第三次构造-1" class="headerlink" title="第三次构造"></a>第三次构造</h6><ol>
<li>队首出队，所以<code>&lt;v2,v5&gt;</code>边出队</li>
</ol>
<pre class="mermaid">graph LR
    v56((V5,V6,6))
    v32((v3,v2,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v36((v3,v6,4))
    v25((v2,v5,3))
    v14((v1,v4,5))
    v12((v1,v2,6))
v25---v36
v36---v14
v14---v34
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v2</code>  <code>v5</code>的代表元，很明显不同,所以将<code>&lt;v2,v5&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph TD
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5</pre>

<ol start="3">
<li>合并代表元,修改等于代表元值为5的代表元的值，改为<code>v2</code>的代表元的值即2</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,4]
    v5[v5,2]
    v6[v6,4]</pre>



<h6 id="第三次构造-2"><a href="#第三次构造-2" class="headerlink" title="第三次构造"></a>第三次构造</h6><ol>
<li>队首<code>&lt;v3,v6&gt;</code>出队</li>
</ol>
<pre class="mermaid">graph LR
    v56((v5,V6,6))
    v32((v3,v2,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v36((v3,v6,4))
    v14((v1,v4,5))
    v12((v1,v2,6))
v36---v14
v14---v34
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v3</code>  <code>v6</code>的代表元，不同,所以将<code>&lt;v3,v6&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5
V3--4---V6</pre>

<ol start="3">
<li>合并代表元,修改等于代表元值为4的代表元的值，改为<code>v3</code>代表元的值即1</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,1]
    v5[v5,2]
    v6[v6,1]</pre>





<h6 id="第四次构造-1"><a href="#第四次构造-1" class="headerlink" title="第四次构造"></a>第四次构造</h6><ol>
<li>队首<code>&lt;v1,v4&gt;</code>出队</li>
</ol>
<pre class="mermaid">graph LR
    v56((V5,V6,6))
    v32((v3,v2,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v14((v1,v4,5))
    v12((v1,v2,6))
v14---v34
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v1</code>  <code>v4</code>的代表元，相同,所以不将<code>&lt;v1,v4&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5
V3--4---V6</pre>

<ol start="3">
<li>此时代表元不进行任何操作</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,1]
    v5[v5,2]
    v6[v6,1]</pre>



<h6 id="第五次构造-1"><a href="#第五次构造-1" class="headerlink" title="第五次构造"></a>第五次构造</h6><ol>
<li>队首<code>&lt;v3,v4&gt;</code>出队</li>
</ol>
<pre class="mermaid">graph LR
    v56((V5,V6,6))
    v32((v3,v2,5))
    v34((v3,v4,5))
    v35((v3,v5,6))
    v12((v1,v2,6))
v34---v32
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v3</code> <code>v4</code>的代表元，相同，所以不将<code>&lt;v3,v4&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5
V3--4---V6</pre>

<ol start="3">
<li>此时代表元不进行任何操作</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,2]
    v3[v3,1]
    v4[v4,1]
    v5[v5,2]
    v6[v6,1]</pre>



<h6 id="第六次构造-1"><a href="#第六次构造-1" class="headerlink" title="第六次构造"></a>第六次构造</h6><ol>
<li><code>&lt;v2,v3&gt;</code>出队</li>
</ol>
<pre class="mermaid">graph LR
    v56((V5,V6,6))
    v32((v3,v2,5))
    v35((v3,v5,6))
    v12((v1,v2,6))
v32---v12
v12---v35
v35---v56</pre>

<ol start="2">
<li>检查<code>v2</code> <code>v3</code>的代表元，不同，所以将<code>&lt;v2,v3&gt;</code>加入T集合中</li>
</ol>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5
V3--4---V6
V3--5---V2</pre>

<ol start="3">
<li>合并代表元,修改等于代表元为2的代表元的值，改为<code>v3</code>代表元的值即1</li>
</ol>
<pre class="mermaid">graph BT
    v1[v1,1]
    v2[v2,1]
    v3[v3,1]
    v4[v4,1]
    v5[v5,1]
    v6[v6,1]</pre>

<p>可以发现，当前T集合中已经有5条边了，最小生成树已经生成完毕。同时观察到，代表元中的值也相同了，表示他们都在同一个子图中了。</p>
<h4 id="算法实现-3"><a href="#算法实现-3" class="headerlink" title="算法实现"></a>算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># kruskal算法，最小生成树，前提该图必须是连通网</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">kruskal</span><span class="params">(self)</span>:</span></span><br><span class="line">    <span class="comment"># 初始化代表元和结果图</span></span><br><span class="line">    result, reps, pqueue, edgesCount = GraphAL(graph=&#123;&#125;), &#123;&#125;, [], <span class="number">0</span></span><br><span class="line">    <span class="keyword">for</span> key <span class="keyword">in</span> self._graph.keys():</span><br><span class="line">        reps[key] = key</span><br><span class="line">    <span class="comment"># 边入队，按优先级排序,选出最短边</span></span><br><span class="line">    <span class="keyword">for</span> key <span class="keyword">in</span> self._graph:</span><br><span class="line">        <span class="keyword">for</span> end <span class="keyword">in</span> self._graph[key].keys():</span><br><span class="line">            edges = self._graph[key][end]</span><br><span class="line">            heapq.heappush(pqueue, (edges, key, end))  <span class="comment"># 边入队</span></span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># 当边数达到n-1条时，即成功得到最小生成树时停止</span></span><br><span class="line">    <span class="keyword">while</span> edgesCount &lt; self.get_vertexNum() - <span class="number">1</span> <span class="keyword">and</span> <span class="keyword">not</span> pqueue.__len__() == <span class="number">0</span>:</span><br><span class="line">        <span class="comment"># 出队</span></span><br><span class="line">        pair = list(heapq.heappop(pqueue))</span><br><span class="line">        <span class="comment"># 判断是否有该顶点,如果没有就要加入</span></span><br><span class="line">        <span class="keyword">if</span> pair[<span class="number">1</span>] <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">            result.add_vertex(pair[<span class="number">1</span>])</span><br><span class="line">        <span class="keyword">if</span> pair[<span class="number">2</span>] <span class="keyword">not</span> <span class="keyword">in</span> result._graph:</span><br><span class="line">            result.add_vertex(pair[<span class="number">2</span>])</span><br><span class="line">        <span class="comment"># 检查两点是否属于不同连通分量</span></span><br><span class="line">        <span class="keyword">if</span> reps[pair[<span class="number">1</span>]] != reps[pair[<span class="number">2</span>]]:</span><br><span class="line">            result.add_edge(pair[<span class="number">1</span>], pair[<span class="number">2</span>], pair[<span class="number">0</span>])</span><br><span class="line">            edgesCount += <span class="number">1</span></span><br><span class="line">            <span class="comment"># 合并连通分量</span></span><br><span class="line">            rep, orep = reps[pair[<span class="number">1</span>]], reps[pair[<span class="number">2</span>]]</span><br><span class="line">            <span class="keyword">for</span> key <span class="keyword">in</span> reps.keys():</span><br><span class="line">                <span class="keyword">if</span> reps[key] == orep:</span><br><span class="line">                    reps[key] = rep</span><br><span class="line">    <span class="keyword">return</span> result</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure>

<h4 id="测试-3"><a href="#测试-3" class="headerlink" title="测试"></a>测试</h4><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831002634.png!blog" alt="20190831002634"></p>
<p>与刚才结果自动推的完全一致。</p>
<pre class="mermaid">graph LR
    V1((v1))
    V3((V3))
    V6((V6))
    V4((V4))
    V2((V2))
    V5((V5))
V1--1---V3
V6--2---V4
V2--3---V5
V3--4---V6
V3--5---V2</pre>





<h2 id="最短路径"><a href="#最短路径" class="headerlink" title="最短路径"></a>最短路径</h2><h3 id="dijkstra算法"><a href="#dijkstra算法" class="headerlink" title="dijkstra算法"></a>dijkstra算法</h3><h4 id="算法原理"><a href="#算法原理" class="headerlink" title="算法原理"></a>算法原理</h4><p>在看迪杰斯特拉算法之前，可以先回顾下BFS算法的过程。BFS的实现是通过一个队列实现。还是这张图</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190825160305.png!blog" alt="20190825160305"></p>
<p>选择假设BFS从A节点开始，A节点出队后，将A的邻接节点B,C入队</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831190937.png!blog" alt="20190831190937"></p>
<p>然后B出队，D入队，C出队，E入队。整个BFS的流程大概如此，在这之中，可以看到BFS队列中不同节点离A的距离，每个出队的结点对于他的邻接节点的距离都是1，并且在队列中他们也是紧紧挨着的。</p>
<p>假如可以把这些顶点进行排序，然后不断更新队中节点到A的距离值，那么应该可以一步步的获得当前节点到A节点的最短距离了。</p>
<p>该算法有两个难点：</p>
<ol>
<li>如何排序</li>
</ol>
<p>我使用的是python的优先队列，该队列是基于堆这一种数据结构实现的，你也可以自行选择排序算法进行排序</p>
<ol start="2">
<li>如何更新距离</li>
</ol>
<p>在BFS中每个节点到A的距离是固定的，是不会发生更新操作的，这是由于BFS算法实现过程中有个访问标志会标志某个节点是否已被访问，该标志保证了每个节点只访问一次。但是在迪杰斯特拉算法中，这样是不行的，因为想要在每个节点出队后，都要将该结点的邻接节点到目标点（这个例子中是A点）的距离进行比较更新，选择权值和小的。</p>
<p>看下面这个网</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831193520.png!blog" alt="20190831193520"></p>
<p>当遍历到B的时候A到B有两条路，一条是A-B，另一条是A-C-B，前者的距离为5，比较长，后者的距离为3（1+2）。在迪杰斯特拉中就会选择路径A-C-B这条路径。</p>
<p>在实际的算法实现中，距离的比较是通过一个<code>distance</code>的列表实现的，该列表距离了每个顶点到目标点的最短距离。然后在下一次遍历中不断得更新这个距离就可以了。</p>
<h5 id="构造过程举例-1"><a href="#构造过程举例-1" class="headerlink" title="构造过程举例"></a>构造过程举例</h5><p>假设还是上面这个图。</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831193520.png!blog" alt="20190831193520"></p>
<p>要求图中顶点到A的最短距离</p>
<h6 id="初始化-1"><a href="#初始化-1" class="headerlink" title="初始化"></a>初始化</h6><p>初始化距离列表,inf 表示无穷，A的目标点，所以距离为0</p>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,inf]
    C[C,inf]
    D[D,inf]
    E[E,inf]
    F[F,inf]</pre>

<p>初始化优先级队列，目标节点A入队</p>
<pre class="mermaid">graph TB
    A((A,0))</pre>



<p>当队列不为空时，循环。</p>
<h6 id="第一次构造-2"><a href="#第一次构造-2" class="headerlink" title="第一次构造"></a>第一次构造</h6><ol>
<li>A出队,并标记为已访问，遍历A的邻接节点B、C，同时将A到B的距离5(0+5)和A到C的距离1(0+1)，与<code>distance</code>列表中的距离进行比较，由于<code>distance</code>中的距离都是无穷，所以<code>distance</code>中C的距离更新为1，B的距离更新为<code>5</code></li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,5]
    C[C,1]
    D[D,inf]
    E[E,inf]
    F[F,inf]</pre>

<ol start="2">
<li>B,C节点由于距离被更新了。需要参与下一次比较，所以B、C入队</li>
</ol>
<pre class="mermaid">graph LR
    B((B,5))
    C((C,1))
C-->B</pre>



<p>第二次构造</p>
<ol>
<li>C出队，并标记为已访问，遍历C的邻接节点A,B,D,E，将C-A的距离1，C-B的距离3(1+2)和C-D的距离5(1+4)和C-E的距离9（1+8），与<code>distance</code>列表中的B,C,E的距离进行比较，更新为其中的较小值</li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,5]
    E[E,9]
    F[F,inf]</pre>

<ol start="2">
<li>由于B,D,E的距离被更新了。需要参与下一次的比较，所以B,C,E需要入队，带着他们的更新后的权值</li>
</ol>
<pre class="mermaid">graph LR
    B((B,5))
    B1((B,3))
    D((D,5))
    E((E,9))

B1-->B
B-->D
D-->E</pre>



<h6 id="第三次构造-3"><a href="#第三次构造-3" class="headerlink" title="第三次构造"></a>第三次构造</h6><ol>
<li>B出队，并标记为已访问，遍历B的子节点D,C,A，将B-D（3+1=4）,B-C（3+2=5）,B-A（3+5）的距离分别与<code>distance</code>中的D,C,A距离进行比较，取小的值，发现只有D的距离被更新为了4</li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,9]
    F[F,inf]</pre>

<ol start="3">
<li>由于D被更新了，需要参与下一次的比较，所以D入队，带着D更新后的权值</li>
</ol>
<pre class="mermaid">graph LR
    D1((D,4))
    B((B,5))
    D((D,5))
    E((E,9))

D1-->B
B-->D
D-->E</pre>



<h6 id="第四次构造-2"><a href="#第四次构造-2" class="headerlink" title="第四次构造"></a>第四次构造</h6><ol>
<li>D出队，并标记为已访问，遍历D的子节点B,C,E,F。将D-B（4+1=5）,D-C（4+4=8）,D-E(4+3=7),D-F(4+6=10)的距离分别与<code>distance</code>中的B,C,E,F距离进行比较，取小的值</li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,7]
    F[F,10]</pre>

<ol start="3">
<li>由于只有E,F的距离被更新为7,和10，所以E，F需要带着他们更新后的权值入队，参与下一次的比较。</li>
</ol>
<pre class="mermaid">graph LR

    B((B,5))
    D((D,5))
    E1((E,7))
    E((E,9))
    F((F,10))

B-->D
D-->E1
E1-->E
E-->F</pre>





<h6 id="第五次构造-2"><a href="#第五次构造-2" class="headerlink" title="第五次构造"></a>第五次构造</h6><ol>
<li>队首B出队，由于B被标记已访问，所以直接扔掉，进入下一个循环</li>
</ol>
<pre class="mermaid">graph LR
    D((D,5))
    E1((E,7))
    E((E,9))
    F((F,10))
D-->E1
E1-->E
E-->F</pre>

<ol start="2">
<li>队首D出队，由于D已经被标记已访问，扔掉。进入下一个循环</li>
</ol>
<pre class="mermaid">graph LR

    E1((E,7))
    E((E,9))
    F((F,10))

E1-->E
E-->F</pre>

<ol start="3">
<li><p>队首E出队，标记为已访问。遍历其邻接节点C,D，将E-C（7+4=11），E-D（7+3=10）与<code>distance</code>中的C,D值进行比较，取小的值，发现C,D都不需要更新。</p>
</li>
<li><p>由于没有节点被更新，所以没有节点入队。此时的<code>distance</code>如下图</p>
</li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,7]
    F[F,10]</pre>





<h6 id="第六次构造-2"><a href="#第六次构造-2" class="headerlink" title="第六次构造"></a>第六次构造</h6><ol>
<li>队首E出队，由于E被标记为已访问，扔掉，进入下一个循环</li>
</ol>
<pre class="mermaid">graph LR
    E((E,9))
    F((F,10))

E-->F</pre>

<ol start="2">
<li>队首E出队，由于E被标记为已访问，扔掉，进入下一个循环</li>
</ol>
<pre class="mermaid">graph LR
    F((F,10))</pre>

<ol start="3">
<li>队首F出队,发现他没有子节点，所以<code>distance</code>不会被更新，队列将不会加入新的结点。此时的<code>distance</code>如下图</li>
</ol>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,7]
    F[F,10]</pre>



<h6 id="第七次构造"><a href="#第七次构造" class="headerlink" title="第七次构造"></a>第七次构造</h6><p>由于此时队列为空，所以循环结束，迪杰斯特拉算法求解完毕！此时的<code>distance</code>就是每个节点到目标点A的最短距离了。</p>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,7]
    F[F,10]</pre>



<p>迪杰斯特拉算法就是基于这种”宽度优先遍历”的思想，按路径的长度选择下一个最短节点然后逐步扩张（这一点也很像用MST性质实现的prim算法）。这个算法在探索中也会更新已经节点的最短路径，每一步都可以找到一个确定的最短路径，这就是典型的动态规划思想（在计算中保留一些信息，用来支持下一步的决策信息）</p>
<h4 id="算法实现-4"><a href="#算法实现-4" class="headerlink" title="算法实现"></a>算法实现</h4><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 迪杰斯特拉法算最短路径</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">dijkstra</span><span class="params">(self, start)</span>:</span></span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> self._invalid(start):</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">"不存在"</span> + start + <span class="string">"这样的顶点"</span>)</span><br><span class="line">    graph = self._graph</span><br><span class="line">    pqueue = []  <span class="comment"># 优先级队列</span></span><br><span class="line">    heapq.heappush(pqueue, (<span class="number">0</span>, start))  <span class="comment"># 根顶点进队，最高优先级</span></span><br><span class="line">    seen = set()  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">    parent = &#123;start: <span class="literal">None</span>&#125;  <span class="comment"># 生成树</span></span><br><span class="line">    distance = self.__init_distance(start)  <span class="comment"># 初始化距离</span></span><br><span class="line">    <span class="keyword">while</span> pqueue.__len__() &gt; <span class="number">0</span>:</span><br><span class="line">        pair = heapq.heappop(pqueue)  <span class="comment"># pop弹出的是元组，第一个参数是距离（优先级），第二个是顶点</span></span><br><span class="line">        dist = pair[<span class="number">0</span>]</span><br><span class="line">        vertex = pair[<span class="number">1</span>]</span><br><span class="line">        seen.add(vertex)  <span class="comment"># 记录访问过的顶点</span></span><br><span class="line">        nodes = graph[vertex].keys()  <span class="comment"># 获取其顶点的邻接顶点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> nodes:</span><br><span class="line">            <span class="keyword">if</span> node <span class="keyword">not</span> <span class="keyword">in</span> seen:</span><br><span class="line">                <span class="keyword">if</span> dist + graph[vertex][node] &lt; distance[node]:  <span class="comment"># 如果当前顶点到开始顶点的距离小于距离列表中的值，更新距离</span></span><br><span class="line">                    heapq.heappush(pqueue, (dist + graph[vertex][node], node))</span><br><span class="line">                    parent[node] = vertex</span><br><span class="line">                    distance[node] = dist + graph[vertex][node]</span><br><span class="line">        <span class="comment"># 输出遍历结果</span></span><br><span class="line">        <span class="comment"># print(vertex)</span></span><br><span class="line">    <span class="keyword">return</span> distance, parent</span><br><span class="line">    <span class="keyword">pass</span></span><br></pre></td></tr></table></figure>

<h4 id="测试-4"><a href="#测试-4" class="headerlink" title="测试"></a>测试</h4><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831205632.png!blog" alt="20190831205632"></p>
<p>可以发现，如刚才推导的结果一模一样。</p>
<pre class="mermaid">graph TB
    A[A,0]
    B[B,3]
    C[C,1]
    D[D,4]
    E[E,7]
    F[F,10]</pre>



<h3 id="弗洛依德算法-待填坑"><a href="#弗洛依德算法-待填坑" class="headerlink" title="弗洛依德算法(待填坑)"></a>弗洛依德算法(待填坑)</h3><h4 id="算法原理-1"><a href="#算法原理-1" class="headerlink" title="算法原理"></a>算法原理</h4><h4 id="算法实现-5"><a href="#算法实现-5" class="headerlink" title="算法实现"></a>算法实现</h4><h4 id="测试-5"><a href="#测试-5" class="headerlink" title="测试"></a>测试</h4><h2 id="拓扑排序"><a href="#拓扑排序" class="headerlink" title="拓扑排序"></a>拓扑排序</h2><h3 id="算法原理-2"><a href="#算法原理-2" class="headerlink" title="算法原理"></a>算法原理</h3><p>拓扑排序是有向图（网）中的内容，只在有向网（图）的范畴中讨论。</p>
<p>先看一个实际生活中可能遇到的问题：选课问题，例如上大一的时候你肯定要先学C语言，然后才能学数据结构。这个时候C语言和数据结构就构成了一个排列问题，<strong>谁在前谁在后</strong>。用图中的顶点表示一个活动，边表示活动之间的顺序关系。这样的图就称为AOV网（顶点活动网）</p>
<p>下图就是一个典型的AOV网实例。</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831210501.png!blog" alt="20190831210501"></p>
<p>任何无回路的AOV网N都可以求解出拓扑序列，方法很简单：</p>
<ul>
<li>从N中选出一个入度为0的顶点作为序列的下一个顶点</li>
<li>从N网中删除所选顶点的出边</li>
<li>重复执行上面两步，直到已经选出了图N的所有顶点</li>
</ul>
<p>拓扑排序算法有两个难点：</p>
<ol>
<li>如何寻找入度为0的顶点</li>
<li>真的需要拷贝整张图，然后进行删除</li>
</ol>
<p>一个显然的办法是不断遍历图，寻找入度为0的顶点。但时间代价会很高。顶点间的制约关系决定了顶点的入度。入度是一个整数，用一个整数表就能记录所以顶点的入度了。因此，我的方法是用一张入度表记录了每个顶点的入度，初始时，表中的各顶点的入度对应为图中顶点的入度，在随后的计算中，一旦选中一个顶点，就将该顶点的出边入度减一。</p>
<p>在实际的算法实现中还用了一个0度栈来记录已经入度为0但还未处理的顶点。</p>
<p>算法比较简单。</p>
<p>可以慢慢调试</p>
<p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831212236.png!blog" alt="20190831212236"></p>
<h3 id="算法实现-6"><a href="#算法实现-6" class="headerlink" title="算法实现"></a>算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">topological_sort</span><span class="params">(self)</span>:</span></span><br><span class="line">    indegree = &#123;&#125;  <span class="comment"># 入度表</span></span><br><span class="line">    zerov = []  <span class="comment"># 利用0度栈记录已知的入度为0的但还未处理的顶点</span></span><br><span class="line">    m = <span class="number">0</span>  <span class="comment"># 输出顶点计数</span></span><br><span class="line">    topo = []  <span class="comment"># 拓扑排序结果</span></span><br><span class="line">    <span class="comment"># 生成入度表和0度栈</span></span><br><span class="line">    <span class="keyword">for</span> vetx <span class="keyword">in</span> self._graph:</span><br><span class="line">        indegree[vetx] = self.get_inEdge(vetx).__len__()</span><br><span class="line">        <span class="keyword">if</span> indegree[vetx] == <span class="number">0</span>:</span><br><span class="line">            zerov.append(vetx)</span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> zerov.__len__() != <span class="number">0</span>:</span><br><span class="line">        Vi = zerov.pop()</span><br><span class="line">        topo.append(Vi)</span><br><span class="line">        m += <span class="number">1</span></span><br><span class="line">        <span class="keyword">for</span> Vj <span class="keyword">in</span> self.get_outEdge(Vi).keys():  <span class="comment"># 对顶点Vi的每个邻接点入度减1，如果Vj的入度变为0，则将Vj入栈，表示Vj就是下一个需要处理的顶点</span></span><br><span class="line">            indegree[Vj] -= <span class="number">1</span></span><br><span class="line">            <span class="keyword">if</span> indegree[Vj] == <span class="number">0</span>:</span><br><span class="line">                zerov.append(Vj)</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> m &lt; self.get_vertexNum():  <span class="comment"># 该有向图有回路</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">False</span></span><br><span class="line">    <span class="keyword">return</span> topo</span><br></pre></td></tr></table></figure>

<h3 id="测试-6"><a href="#测试-6" class="headerlink" title="测试"></a>测试</h3><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/1567257835949.png!blog" alt="1567257835949"></p>
<h2 id="关键路径"><a href="#关键路径" class="headerlink" title="关键路径"></a>关键路径</h2><h3 id="算法原理-3"><a href="#算法原理-3" class="headerlink" title="算法原理"></a>算法原理</h3><h3 id="算法实现-7"><a href="#算法实现-7" class="headerlink" title="算法实现"></a>算法实现</h3><figure class="highlight python"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment"># 关键路径</span></span><br><span class="line"><span class="function"><span class="keyword">def</span> <span class="title">criticalPath</span><span class="params">(self, delay=<span class="number">0</span>)</span>:</span></span><br><span class="line">    topo = self.topological_sort()</span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> topo:</span><br><span class="line">        <span class="keyword">raise</span> GraphError(<span class="string">"存在有向环！"</span>)</span><br><span class="line">    ve = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(len(topo))]  <span class="comment"># 事件最早开始时间</span></span><br><span class="line">    vl = [<span class="number">0</span> <span class="keyword">for</span> i <span class="keyword">in</span> range(len(topo))]  <span class="comment"># 事件最迟开始时间</span></span><br><span class="line">    cp = []  <span class="comment"># 关键路径</span></span><br><span class="line">    result = &#123;&#125;  <span class="comment"># 返回结果</span></span><br><span class="line">    <span class="comment"># --------------------------------计算事件的最早发生时间-----------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(topo.__len__()):</span><br><span class="line">        start = topo[i]  <span class="comment"># 取出拓扑节点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_outEdge(start).keys():  <span class="comment"># 获取拓扑节点的邻接点，计算ve</span></span><br><span class="line">            w = self._graph[start][node]  <span class="comment"># 当前节点与邻接节点的边</span></span><br><span class="line">            j = topo.index(node)  <span class="comment"># 邻接节点的下标</span></span><br><span class="line">            <span class="keyword">if</span> ve[j] &lt; ve[i] + w:  <span class="comment"># 更新邻接点的最早发生时间，选大的时间</span></span><br><span class="line">                ve[j] = ve[i] + w</span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># --------------------------------计算事件的最晚发生时间-----------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(topo.__len__()):  <span class="comment"># 给每个事件的最迟发生时间置初值，初值为最早发生时间中的最大值</span></span><br><span class="line">        vl[i] = ve[topo.__len__() - <span class="number">1</span>] + delay</span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> reversed(range(topo.__len__())):</span><br><span class="line">        k = topo[i]  <span class="comment"># 取出拓扑节点</span></span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_inEdge(k).keys():  <span class="comment"># 获取拓扑节点的逆邻接点，计算vl</span></span><br><span class="line">            w = self._graph[node][k]  <span class="comment"># 逆邻接点和当前节点的边</span></span><br><span class="line">            j = topo.index(node)  <span class="comment"># 逆邻接点的下标</span></span><br><span class="line">            <span class="keyword">if</span> vl[j] &gt; vl[i] - w:  <span class="comment"># 更新逆邻接点的最晚发生时间，选小的时间</span></span><br><span class="line">                vl[j] = vl[i] - w</span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line">    <span class="comment"># --------------------------------判断每一活动是否为关键路径--------------------------</span></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(topo.__len__()):</span><br><span class="line">        start = topo[i]</span><br><span class="line">        <span class="keyword">for</span> node <span class="keyword">in</span> self.get_outEdge(start).keys():</span><br><span class="line">            j = topo.index(node)  <span class="comment"># 获得邻接顶点的下标</span></span><br><span class="line">            w = self._graph[start][node]  <span class="comment"># 当前节点与邻接节点的边</span></span><br><span class="line">            e = ve[i]  <span class="comment"># 计算活动&lt;start,node&gt;的最早开始时间</span></span><br><span class="line">            l = vl[j] - w - delay  <span class="comment"># 计算活动&lt;start,node&gt;的最晚开始时间</span></span><br><span class="line">            <span class="keyword">if</span> e == l:</span><br><span class="line">                cp.append((start, node))  <span class="comment"># 如果相等就说明为关键路径</span></span><br><span class="line">            <span class="keyword">pass</span></span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span> i <span class="keyword">in</span> range(topo.__len__()):</span><br><span class="line">        result[topo[i]] = (ve[i], vl[i])</span><br><span class="line">        <span class="keyword">pass</span></span><br><span class="line">    <span class="keyword">return</span> result, cp</span><br></pre></td></tr></table></figure>

<h3 id="测试-7"><a href="#测试-7" class="headerlink" title="测试"></a>测试</h3><p><img src="https://zhong-blog.oss-cn-shenzhen.aliyuncs.com/blog/20190831212504.png!blog" alt="20190831212504"></p>
<script src="https://cdnjs.cloudflare.com/ajax/libs/raphael/2.2.7/raphael.min.js"></script><script src="https://cdnjs.cloudflare.com/ajax/libs/flowchart/1.6.5/flowchart.min.js"></script><textarea id="flowchart-0-code" style="display: none">st=>start: 初始化队列，初始顶点入队
e=>end: 结束BFS
deque=>operation: 出队
isVisit=>condition: 是否访问过该顶点?
visit=>inputoutput: 访问
jump=>operation: 跳过该顶点的访问
isqueNull=>condition: 是否队空

st->deque->isVisit
isVisit(yes)->jump->isqueNull
isVisit(no)->visit->isqueNull
isqueNull(yes)->e
isqueNull(no)->deque</textarea><textarea id="flowchart-0-options" style="display: none">{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}</textarea><script>  var code = document.getElementById("flowchart-0-code").value;  var options = JSON.parse(decodeURIComponent(document.getElementById("flowchart-0-options").value));  var diagram = flowchart.parse(code);  diagram.drawSVG("flowchart-0", options);</script><textarea id="flowchart-1-code" style="display: none">st=>start: 初始化栈，初始顶点进栈
e=>end: 结束DFS
deque=>operation: 出栈
isVisit=>condition: 是否访问过该顶点?
visit=>inputoutput: 访问
jump=>operation: 跳过该顶点的访问
isqueNull=>condition: 是否栈空

st->deque->isVisit
isVisit(yes)->jump->isqueNull
isVisit(no)->visit->isqueNull
isqueNull(yes)->e
isqueNull(no)->deque</textarea><textarea id="flowchart-1-options" style="display: none">{"scale":1,"line-width":2,"line-length":50,"text-margin":10,"font-size":12}</textarea><script>  var code = document.getElementById("flowchart-1-code").value;  var options = JSON.parse(decodeURIComponent(document.getElementById("flowchart-1-options").value));  var diagram = flowchart.parse(code);  diagram.drawSVG("flowchart-1", options);</script>
    </div>

    
    
    
      
  <div class="popular-posts-header">相关文章推荐</div>
  <ul class="popular-posts">
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="\2019\09\03\AOE网及关键路径\" rel="bookmark">AOE网及关键路径实现</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="\2019\09\03\图的遍历-BFS和DFS\" rel="bookmark">图的遍历:BFS和DFS</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="\2019\09\02\图的存储结构实现：邻接表\" rel="bookmark">图的存储结构实现：邻接表</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="\2019\09\03\拓扑排序及实现\" rel="bookmark">拓扑排序及实现</a></div>
      
    </li>
  
    <li class="popular-posts-item">
      
      
      <div class="popular-posts-title"><a href="\2019\09\03\最小生成树-Prim算法实现\" rel="bookmark">最小生成树:Prim算法实现</a></div>
      
    </li>
  
  </ul>


    
    <div>
      
      <div>
    
        <div style="text-align:center;color: #ccc;font-size:14px;">-------------本文结束感谢您的阅读,如有疑问，请联系<a href="mailto:610596547@qq.com">610596547@qq.com</a>-------------</div>
    
</div>
      
    </div>
        
      

      <footer class="post-footer">
          
            
          
          <div class="post-tags">
            
              <a href="/tags/数据结构/" rel="tag"># 数据结构</a>
            
          </div>
        

        

          <div class="post-nav">
            <div class="post-nav-next post-nav-item">
              
                <a href="/2019/08/19/Vim常用操作/" rel="next" title="Vim常用操作及使用技巧">
                  <i class="fa fa-chevron-left"></i> Vim常用操作及使用技巧
                </a>
              
            </div>

            <span class="post-nav-divider"></span>

            <div class="post-nav-prev post-nav-item">
              
                <a href="/2019/09/02/图的存储结构实现：邻接表/" rel="prev" title="图的存储结构实现：邻接表">
                  图的存储结构实现：邻接表 <i class="fa fa-chevron-right"></i>
                </a>
              
            </div>
          </div>
        
      </footer>
    
  </div>
  
  
  
  </article>

  </div>


          </div>
          

        </div>
          
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap">
            文章目录
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview-wrap">
            站点概览
          </li>
        </ul>
      

      <div class="site-overview-wrap sidebar-panel">
        <div class="site-overview">

          <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
      src="/images/profile.jpg"
      alt="钟浩伟">
  <p class="site-author-name" itemprop="name">钟浩伟</p>
  <div class="site-description motion-element" itemprop="description"></div>
</div>
  <nav class="site-state motion-element">
      <div class="site-state-item site-state-posts">
        
          <a href="/archives/">
        
          <span class="site-state-item-count">44</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-categories">
        
          
            <a href="/categories/">
          
        
        
        
          
        
          
        
          
        
          
        
          
        
          
        
        <span class="site-state-item-count">6</span>
        <span class="site-state-item-name">分类</span>
        </a>
      </div>
    
      
      
      <div class="site-state-item site-state-tags">
        
          
            <a href="/tags/">
          
        
        
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
          
        
        <span class="site-state-item-count">15</span>
        <span class="site-state-item-name">标签</span>
        </a>
      </div>
    
  </nav>
  <div class="links-of-author motion-element">
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://github.com/XiaoZhong233" title="GitHub &rarr; https://github.com/XiaoZhong233" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="mailto:601596547@qq.com" title="E-Mail &rarr; mailto:601596547@qq.com" rel="noopener" target="_blank"><i class="fa fa-fw fa-envelope"></i>E-Mail</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="https://blog.csdn.net/weixin_41154636" title="CSDN &rarr; https://blog.csdn.net/weixin_41154636" rel="noopener" target="_blank"><i class="fa fa-fw fa-book"></i>CSDN</a>
      </span>
    
      <span class="links-of-author-item">
      
      
        
      
      
        
      
        <a href="http://profile.zhonghaowei.xyz/" title="Profile &rarr; http://profile.zhonghaowei.xyz/" rel="noopener" target="_blank"><i class="fa fa-fw fa-address-card-o"></i>Profile</a>
      </span>
    
  </div>



        </div>
      </div>
      <!--noindex-->
        <div class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc">

            
            
            
            

            
              <div class="post-toc-content"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#前言"><span class="nav-number">1.</span> <span class="nav-text">前言</span></a></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图的存储结构实现"><span class="nav-number">2.</span> <span class="nav-text">图的存储结构实现</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#邻接矩阵实现（不重要也不好用）"><span class="nav-number">2.1.</span> <span class="nav-text">邻接矩阵实现（不重要也不好用）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#邻接表实现1（基于邻接矩阵，不好用）"><span class="nav-number">2.2.</span> <span class="nav-text">邻接表实现1（基于邻接矩阵，不好用）</span></a></li><li class="nav-item nav-level-2"><a class="nav-link" href="#邻接表实现2-基于字典实现，好用"><span class="nav-number">2.3.</span> <span class="nav-text">邻接表实现2 (基于字典实现，好用)</span></a></li></ol></li><li class="nav-item nav-level-1"><a class="nav-link" href="#图的一些算法实现"><span class="nav-number">3.</span> <span class="nav-text">图的一些算法实现</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#图的遍历"><span class="nav-number">3.1.</span> <span class="nav-text">图的遍历</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#BFS（广度优先搜索）"><span class="nav-number">3.1.1.</span> <span class="nav-text">BFS（广度优先搜索）</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理及步骤"><span class="nav-number">3.1.1.1.</span> <span class="nav-text">算法原理及步骤</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法流程"><span class="nav-number">3.1.1.2.</span> <span class="nav-text">算法流程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现"><span class="nav-number">3.1.1.3.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试"><span class="nav-number">3.1.1.4.</span> <span class="nav-text">测试</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#DFS（深度优先搜索）"><span class="nav-number">3.1.2.</span> <span class="nav-text">DFS（深度优先搜索）</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理及步骤-1"><span class="nav-number">3.1.2.1.</span> <span class="nav-text">算法原理及步骤</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法流程-1"><span class="nav-number">3.1.2.2.</span> <span class="nav-text">算法流程</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现-1"><span class="nav-number">3.1.2.3.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试-1"><span class="nav-number">3.1.2.4.</span> <span class="nav-text">测试</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#存储结构"><span class="nav-number">3.1.2.4.1.</span> <span class="nav-text">存储结构</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#测试结果"><span class="nav-number">3.1.2.4.2.</span> <span class="nav-text">测试结果</span></a></li></ol></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最小生成树"><span class="nav-number">3.2.</span> <span class="nav-text">最小生成树</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#Prim算法"><span class="nav-number">3.2.1.</span> <span class="nav-text">Prim算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理及算法流程"><span class="nav-number">3.2.1.1.</span> <span class="nav-text">算法原理及算法流程</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#原理："><span class="nav-number">3.2.1.1.1.</span> <span class="nav-text">原理：</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#构造过程举例"><span class="nav-number">3.2.1.1.2.</span> <span class="nav-text">构造过程举例</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#第一次构造"><span class="nav-number">3.2.1.1.2.1.</span> <span class="nav-text">第一次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第二次构造"><span class="nav-number">3.2.1.1.2.2.</span> <span class="nav-text">第二次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第三次构造"><span class="nav-number">3.2.1.1.2.3.</span> <span class="nav-text">第三次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第四次构造"><span class="nav-number">3.2.1.1.2.4.</span> <span class="nav-text">第四次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第五次构造"><span class="nav-number">3.2.1.1.2.5.</span> <span class="nav-text">第五次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第六次构造"><span class="nav-number">3.2.1.1.2.6.</span> <span class="nav-text">第六次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#最终结果"><span class="nav-number">3.2.1.1.2.7.</span> <span class="nav-text">最终结果</span></a></li></ol></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现-2"><span class="nav-number">3.2.1.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试-2"><span class="nav-number">3.2.1.3.</span> <span class="nav-text">测试</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#克鲁斯卡尔算法"><span class="nav-number">3.2.2.</span> <span class="nav-text">克鲁斯卡尔算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理及流程"><span class="nav-number">3.2.2.1.</span> <span class="nav-text">算法原理及流程</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#原理"><span class="nav-number">3.2.2.1.1.</span> <span class="nav-text">原理</span></a></li><li class="nav-item nav-level-5"><a class="nav-link" href="#构成过程举例"><span class="nav-number">3.2.2.1.2.</span> <span class="nav-text">构成过程举例</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#初始化"><span class="nav-number">3.2.2.1.2.1.</span> <span class="nav-text">初始化</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第一次构造-1"><span class="nav-number">3.2.2.1.2.2.</span> <span class="nav-text">第一次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第二次构造-1"><span class="nav-number">3.2.2.1.2.3.</span> <span class="nav-text">第二次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第三次构造-1"><span class="nav-number">3.2.2.1.2.4.</span> <span class="nav-text">第三次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第三次构造-2"><span class="nav-number">3.2.2.1.2.5.</span> <span class="nav-text">第三次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第四次构造-1"><span class="nav-number">3.2.2.1.2.6.</span> <span class="nav-text">第四次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第五次构造-1"><span class="nav-number">3.2.2.1.2.7.</span> <span class="nav-text">第五次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第六次构造-1"><span class="nav-number">3.2.2.1.2.8.</span> <span class="nav-text">第六次构造</span></a></li></ol></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现-3"><span class="nav-number">3.2.2.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试-3"><span class="nav-number">3.2.2.3.</span> <span class="nav-text">测试</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#最短路径"><span class="nav-number">3.3.</span> <span class="nav-text">最短路径</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#dijkstra算法"><span class="nav-number">3.3.1.</span> <span class="nav-text">dijkstra算法</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理"><span class="nav-number">3.3.1.1.</span> <span class="nav-text">算法原理</span></a><ol class="nav-child"><li class="nav-item nav-level-5"><a class="nav-link" href="#构造过程举例-1"><span class="nav-number">3.3.1.1.1.</span> <span class="nav-text">构造过程举例</span></a><ol class="nav-child"><li class="nav-item nav-level-6"><a class="nav-link" href="#初始化-1"><span class="nav-number">3.3.1.1.1.1.</span> <span class="nav-text">初始化</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第一次构造-2"><span class="nav-number">3.3.1.1.1.2.</span> <span class="nav-text">第一次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第三次构造-3"><span class="nav-number">3.3.1.1.1.3.</span> <span class="nav-text">第三次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第四次构造-2"><span class="nav-number">3.3.1.1.1.4.</span> <span class="nav-text">第四次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第五次构造-2"><span class="nav-number">3.3.1.1.1.5.</span> <span class="nav-text">第五次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第六次构造-2"><span class="nav-number">3.3.1.1.1.6.</span> <span class="nav-text">第六次构造</span></a></li><li class="nav-item nav-level-6"><a class="nav-link" href="#第七次构造"><span class="nav-number">3.3.1.1.1.7.</span> <span class="nav-text">第七次构造</span></a></li></ol></li></ol></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现-4"><span class="nav-number">3.3.1.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试-4"><span class="nav-number">3.3.1.3.</span> <span class="nav-text">测试</span></a></li></ol></li><li class="nav-item nav-level-3"><a class="nav-link" href="#弗洛依德算法-待填坑"><span class="nav-number">3.3.2.</span> <span class="nav-text">弗洛依德算法(待填坑)</span></a><ol class="nav-child"><li class="nav-item nav-level-4"><a class="nav-link" href="#算法原理-1"><span class="nav-number">3.3.2.1.</span> <span class="nav-text">算法原理</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#算法实现-5"><span class="nav-number">3.3.2.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-4"><a class="nav-link" href="#测试-5"><span class="nav-number">3.3.2.3.</span> <span class="nav-text">测试</span></a></li></ol></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#拓扑排序"><span class="nav-number">3.4.</span> <span class="nav-text">拓扑排序</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法原理-2"><span class="nav-number">3.4.1.</span> <span class="nav-text">算法原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现-6"><span class="nav-number">3.4.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#测试-6"><span class="nav-number">3.4.3.</span> <span class="nav-text">测试</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#关键路径"><span class="nav-number">3.5.</span> <span class="nav-text">关键路径</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#算法原理-3"><span class="nav-number">3.5.1.</span> <span class="nav-text">算法原理</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#算法实现-7"><span class="nav-number">3.5.2.</span> <span class="nav-text">算法实现</span></a></li><li class="nav-item nav-level-3"><a class="nav-link" href="#测试-7"><span class="nav-number">3.5.3.</span> <span class="nav-text">测试</span></a></li></ol></li></ol></li></ol></div>
            

          </div>
        </div>
      <!--/noindex-->
      



    </div>
  </aside>
  <div id="sidebar-dimmer"></div>




      </div>
    </main>

    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright">&copy; <span itemprop="copyrightYear">2020</span>
  <span class="with-love" id="animate">
    <i class="fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">钟浩伟</span>
</div>


<div id="days"></div>
<div class="BbeiAn-info">
   	粤ICP备 -
    <a target="_blank" href="http://beian.miit.gov.cn" style="color:#f0d784"  rel="nofollow">粤ICP备19111001号-1</a> <!--a标签中增加nofollow属性，避免爬虫出站。-->| 
	<a target="_blank" href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=" style="color:#f0d784;text-decoration:none;padding-left:30px;background:url(https://s1.ax1x.com/2018/09/29/ilmwIH.png) no-repeat left center" rel="nofollow">粤公网安备 粤ICP备19111001号-1</a>	  <!--这里将图标作为了背景，以使得能和后面的文字在同一行-->
</div>

<script>
function show_date_time(){
    window.setTimeout("show_date_time()", 1000);
    BirthDay=new Date("08/15/2019 22:40:14");
    today=new Date();
    timeold=(today.getTime()-BirthDay.getTime());
    sectimeold=timeold/1000
    secondsold=Math.floor(sectimeold);
    msPerDay=24*60*60*1000
    e_daysold=timeold/msPerDay
    daysold=Math.floor(e_daysold);
    e_hrsold=(e_daysold-daysold)*24;
    hrsold=setzero(Math.floor(e_hrsold));
    e_minsold=(e_hrsold-hrsold)*60;
    minsold=setzero(Math.floor((e_hrsold-hrsold)*60));
    seconds=setzero(Math.floor((e_minsold-minsold)*60));
    document.getElementById('days').innerHTML="<p>小破站已运行 "+daysold+" 天 "+hrsold+" 小时 "+minsold+" 分 "+seconds+" 秒</p>";
}
function setzero(i) {
    if (i<10) {
        i="0" + i
    };
    return i;
}
show_date_time();
</script>

        








        
      </div>
    </footer>
      <div class="back-to-top">
        <i class="fa fa-arrow-up"></i>
          <span id="scrollpercent"><span>0</span>%</span>
        
      </div>

    

  </div>

  
  <script src="/lib/jquery/index.js?v=3.4.1"></script>

<script src="/js/utils.js?v=7.3.0"></script>

<script src="/js/schemes/pisces.js?v=7.3.0"></script>



<script src="/js/next-boot.js?v=7.3.0"></script>




  















  <script src="/js/local-search.js?v=7.3.0"></script>










<script>
if (document.querySelectorAll('pre.mermaid').length) {
  NexT.utils.getScript('//cdn.jsdelivr.net/npm/mermaid@8/dist/mermaid.min.js', () => {
    mermaid.initialize({
      theme: 'default',
      logLevel: 3,
      flowchart: { curve: 'linear' },
      gantt: { axisFormat: '%m/%d/%Y' },
      sequence: { actorMargin: 50 }
    });
  }, window.mermaid);
}
</script>




  

  

  


  
  <script src="/js/scrollspy.js?v=7.3.0"></script>
<script src="/js/post-details.js?v=7.3.0"></script>



  
  <script type="text/javascript" src="//cdn.bootcss.com/canvas-nest.js/1.0.0/canvas-nest.min.js"></script>
  
<script src="/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"pluginRootPath":"live2dw/","pluginJsPath":"lib/","pluginModelPath":"assets/","tagMode":false,"log":false,"model":{"jsonPath":"/live2dw/assets/assets/hijiki.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":false}});</script></body>
</html>
